This application is a national phase of PCT/FR99/01402 which was filed on Jun. 14, 1999 and was published by the International Bureau in English on Dec. 23, 1999.
The invention relates to a method of searching for images, each one of which has been recorded in a data base in the form of a structured information index and in a way that favors a subsequent search for a specified element in the images of this data base.
A simple technique used to search for a specified detail in an image consists of consulting a catalogue that describes the image using text or using key words, but the drawing up of the catalogue takes time and it is not possible to guarantee that the images will be described with objectivity and that the details in which one will be interested in the future will be perceived at the time. Finally, the description will not generally be precise enough since the details will generally be identified by their category (building, vehicle, individual person, etc.) while in general a particular individual item will be asked for from this category, which will require examination of all the images in which this category of elements is present.
Another solution consists of looking for an object by describing its outline shape and its texture and looking for this in the data bank of images. It is then necessary to extract the corresponding information on digital modeling of the images broken down into points. Unfortunately, no extraction method exists for the outline or texture of an object which is effective in all cases, and these methods result in failure when the objects are partially masked or when they are illuminated to different extents in the sample provided for the search and in the image in which this sample must be discovered.
Another method consists of comparing the sample provided with each of the parts of each of the images, the comparison resting on the tints of the points of the sample and the points of the images. However, this method is impractical for a search that is at all large.
A final category of methods, to which the invention belongs, consists of modeling the images by means of an index that represents characteristics of the image. The sample to be looked for will be modeled in the same way in order to give an index in analog form and the comparison will rest on the indices. If a comparison is judged to be positive, the corresponding image will be extracted and examined.
Recently there has been much interest in the compression of images using their fractal properties, in order to provide indices which occupy little memory space while permitting subsequent reconstruction of an image of satisfactory quality; these indices can, as will be seen, be used in the invention for comparisons leading to the search for samples provided that certain precautions are taken when they are drawn up.
A fractal object has the property of being identical to its parts: if a fragment of it is isolated and enlarged, it is found to be identical to the initial object. The image of a fractal object can be obtained by applying certain geometrical transformations repeatedly to a starting image, which is then deformed to converge towards the image of the fractal object that is called the attractor of the geometric transformation. The starting image can be chosen in any fashion whatsoever.
Normal images are not fractal images, but it is nevertheless possible to find quite simple geometrical transformations for which these images are attractors. The image can then be reconstituted by simply knowing an index that expresses these geometric transformations and applying these transformations several times to any starting image whatsoever: it is then enough to simply record the index in the data base, without it being necessary to record the image itself in digital form, which would take up much more space.
In practice, the geometric transformations are determined by dividing the image into sectors or ranges and making a domain of the same image, that is to say another part of the image, correspond to each of these ranges. In practice, this other part of the image has a greater surface area since suitable geometric transformations should contract or shrink the details on which they act. The correlations by which the ranges and the domains are made to relate to one another are chosen so that the domains resemble the ranges with which they are associated, that is to say that they have a similar appearance once they have possibly had certain modifications made to them, modifications of luminosity, contrast and color, or modifications of shape through rotation or through symmetry.
It is essential that the indices of the images and the samples in these images to be looked for, are at least partially composed in the same way, that is to say that homologous ranges are related to homologous domains, so that they are comparable. With regard to this, an important risk is linked to the sizes of the image and the sample which are often very different the domains and ranges that are made to correspond in the sample through a fractal transform are generally close to one another, while in a large size image they can be much further apart; corresponding ranges of the sample and the image will then be associated with different domains, that of the index and the image being outside the sample if precautions have not been taken.
It is not then possible for corresponding parts of the sample and image indices to be identical, and the search will be unfruitful if this circumstance occurs too often. With regard to this, one should make it clear that the domains associated with one and the same range by the indices of the sample and the image are chosen arbitrarily in most of the known methods, which means that these domains are generally different in any case and that the presence of the sample in the image should be taken as being probable if just a few fragments of their indices are identical. However the disadvantages of this situation are much more accentuated if the problem indicated above has not been resolved.
French patent application No. 96.11751 of the Sep. 26, 1996 provides one solution: a decision is made to limit the distance between each of the ranges of the images and the domains which are respectively associated with them through the index. This enables one to associate a specified range with identical domains of the image and of the sample with greater probability. The risks of an unfruitful comparison of the indices when the sample is indeed present in the image being examined are thereby reduced.
However, other risks of failing to make a comparison are not avoided by proceeding in this way: since the geometric transformations are normally defined by Cartesian co-ordinates which express the distance between the ranges and the domains related to them, the comparison will not be possible if the sample and the image are viewed from different angles and therefore have different co-ordinate axes. It is also necessary to ensure that the division of the sample and the image into domains and ranges are comparable without dividing up the image or the sample in too arbitrary a fashion, that is to say by avoiding splitting the essential details or by associating very different portions of elements inside one and the same domain or one and the same range.
The invention has been designed to remedy these difficulties. It consists of combining certain techniques of the art of modeling imagesxe2x80x94some of which are known individuallyxe2x80x94with a method of composing the index, the idea of which resembles that of the previous application but which is less arbitrary and more methodical, so as to construct the indices in a substantially invariant fashion, that is to say independent of any interference which could affect the image. Hence, the indices of the sample to be looked for and the images in which it is present will resemble one another even if the images have been subject to noise and if the sample does not appear in the same way.
Noise, defects and interference of the images exert an influence that is just as great on the indices based on properties other than the fractals. The objective of the invention is to be free from this influence to a large degree by making the indices invariant or independent of slight interference which can affect the images and compromise the comparisons.
Instead of the divisions of the image being arbitrary and regular, as is the case in numerous methods where the image is divided into similar rectangles, the divisions are defined by points of interest which correspond to places where the images have properties which vary greatly and which, in practice, are generally positioned at the angles of details represented on the image. Hence these divisions better follow the outlines of the details and the properties extracted from their contents will be more homogeneous, which will allow them to be better defined and hence better compared with less uncertainty. Furthermore, by ensuring that the index is constructed either with the contents of the portion being considered or with that of neighboring portions, that is to say defined portions, an important arbitrary element in the construction of the indices is removed since it will no longer be possible to choose the domains and the ranges made to correspond by a fractal transform, which is beneficial to the quality of the image to be reconstructed but harms the comparisons.
However, this will not allow one to obtain an invariance of the indices since the points of interest, which are the basis for the non-uniform division of the image, are still sensitive to noise or other photographic conditions of the kind which cannot be avoided since they depend on the circumstances under which each image was created. The image divisions will be modified as a consequence and the invariance of the indices will therefore be affected. However, it will be seen that this harmful effect will be considerably attenuated if the intersections of the link lines are used as possible vertices of the polygons forming the portions of the image and if these polygons can partially or totally cover one another, encroaching one upon the other, something that is not retained in the usual methods where the indices are not used for the purposes of making comparisons but only to reconstruct the images.
The index itself can express fractal properties of the image. In this case, it conforms to the invention when the index expresses the relating of different portions of the image having comparable appearances, the different portions comprising the divisions of the image and sub-divisions of the image obtained by dividing up the divisions, each of the sub-divisions being related in the index with each of the divisions adjacent to the division which contains said sub-division, said adjacent divisions constituting said neighboring portions.
However, it can also express properties intrinsic to the portions of the image themselves. It is then proposed to express them in the index in the form of mathematical moments which permit the quantifying of these properties and contribute to ensuring the invariance of the indices. These moments are preferably sums, over each of the image portions, of terms calculated for each point of said image portion which are proportional to a parameter expressing one aspect of the point and to a power determined for a barycentric co-ordinate of the said point.
The barycentric co-ordinates can further be employed to calculate types of index other than mathematical moments, for example the Fourier transforms; their advantage is that they are linked to the shape of portions from division of the image, and therefore they stem indirectly from the points of interest and from the elements of the image, but not from either the orientation or the position of the elements in the image.